package com.algorithms.sorts;

/**
 * InsertionSort take the complexity O(N^2)<br><br>
 * 
 * we assume having a partial increasing sorted list at the left of array,
 * for every single item after that we will insert into that list and shift
 * all greater elements from that list to the right for 1 item.<br><br> 
 * 
 * this algorithm is similar to <b>SelectionSort</b> but we don't make all 
 * comparisons with all items of left sorted list. only items has greater value
 * will be used for comparing and shifting.<br><br>
 * 
 * this algorithm run faster than <b>SelectionSort</b> since they consume 
 * less comparisons and no swapping, only inserting.
 * 
 * @author minhld
 *
 */
public class InsertionSort extends Sort{
	
	public InsertionSort(int[] dataArray, int dataLength){
		super(dataArray, dataLength);
		this.sortName = "InsertionSort";
	}
	
	@Override
	public int[] sort(){
		int marker, insertIndex = -1, backIndex = -1;
		
		for (int i = 1; i < this.length; i++){
			marker = this.data[i];
			backIndex = i - 1;
			insertIndex = -1;
			
			while (backIndex >= 0 && marker < this.data[backIndex]){
				// shift 1 left element to the right
				this.data[backIndex + 1] = this.data[backIndex];
				
				// mark up the insert position
				insertIndex = backIndex;
				backIndex--;
				
				this.numOfCopy++;
				this.numOfProcess++;
			}
			
			if (insertIndex >= 0){
				this.data[insertIndex] = marker;
				
				this.numOfCopy++;
			}
			
			this.numOfProcess++;
		}
		
		return this.data;
	}
}
